package com.justnow.offer;

import java.util.HashMap;

public class Solution560 {
    /**
     * 方法一：O(n^2)
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) { //start为子数组的尾部下标
            int sum = 0;
            for (int end = start; end >= 0; --end) { //end作为start从右到左依次求和的坐标
                //举例数组:[2, -1, 3]
                //当start为2时
                //sum的值依次为：
                //sum = nums[2]
                //sum = nums[2] + nums[1];
                //sum = nums[2] + nums[1] + nums[0]
                //当start为1时
                //sum的值依次为：
                //sum = nums[1]
                //sum = nums[1] + nums[0]
                //当start为0时
                //sum的值依次为：
                //sum = nums[0]。这样就可以求出所有和为k的子数组
                sum += nums[end];
                if (sum != k) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 方法二，使用前缀和与哈希
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum2(int[] nums, int k) {
        int n = nums.length;
        //map: 前缀和 -> 该前缀和出现的次数
        HashMap<Integer, Integer> preSum = new HashMap<>();
        //前缀和最前面的0
        preSum.put(0, 1);

        int ans = 0, sum0_i = 0;
        for (int i = 0; i < n; i++) {
            sum0_i += nums[i];
            //判断是否存在等于0的情况为，sum0_i - sum0_j = k;，所以，我们想要找的前缀和为
            int sum0_j = sum0_i - k;
            //如果前面有这个前缀和，则直接更新答案
            if (preSum.containsKey(sum0_j))
                ans += preSum.get(sum0_j);
            // 把前缀和nums[0...i]加入并记录出现次数,因为需要将前缀和加入到hashMap中
            //preSum.getOrDefault(sum0_i, 0) 如果preSum这个map中不存在sum0_i，那么直接将0当做value，否则返回对应的value
            preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0) + 1);
            
        }
        return ans;
    }
}
